1. Field of the Invention
This invention relates to shifters or rotators, and more particularly to a method and circuit for shifting or rotating operands of multiple size.
2. Description of the Relevant Art
Microprocessors determine the speed and power of personal computers, and a growing number of more powerful machines, by handling most of the data processing in the machine. Microprocessors typically include at least three functional groups: the input output unit (I/O), the control unit and the arithmetic logic unit (ALU). The I/O unit interfaces between external circuitry and the ALU and the control unit. I/O units frequently include signal buffers for increasing the current capacity of the signal before the signal is sent to external components. The control unit controls the operation of the microprocessor by fetching instructions from the I/O unit and translating the instructions into a form that can be understood by the ALU. In addition, the control unit keeps track of which step of the control unit is being executed. The ALU handles the mathematical computations and logical operations that are performed by the microprocessor. The ALU executes the decoded instructions received from the control unit to modify data contained in registers within the processor.
Essential components of any ALU include the operand shifter and operand rotator. The shifter generally operates to shift an operand left or right by x bits with zero fill. The rotator generally operates to rotate an operand left or right by x bits. Often times, the shifter and rotator are combined into a single shifter/rotator circuit in order to conserve the physical size of the ALU. Furthermore, the shifter/rotator can be constructed and operated to shift or rotate operands of multiple size to avoid employing several shifter/rotators each designated for use on operands of a single size.
FIG. 1 illustrates a prior art shifter/rotator 10 capable of shifting or rotating eight bit or four bit operands either left or right depending upon the control signals inputted thereto and how the shifter/rotator 10 is loaded. Generally, shifter/rotator 10 is a double left shifter configured to also right shift operands provided thereto as will be more fully explained below. Shifter/rotator 10 includes a pre-shift stage 12 which has two functions one of which is to pre-shift four bit operands so that they are properly aligned for a rotation operation. Shifter/rotator 10 also includes a first shifting stage 14 for shifting operands provided thereto by one bit, second shifting stage 16 for shifting operands provided thereto by two bits, and third shifting stage 18 for shifting operands provided thereto by four bits. Shifter/rotator 10 is arranged so that the first, second, and third shifting stages 14, 16, and 18, respectively, receive the result operand of the pre-shifting, first, and second shifting stages, respectively.
Shifter/rotator 10 further includes upper input nodes 20, lower input nodes 22, and output nodes 26. The eight output nodes 26 provide the results of shifting or rotating an eight bit operand, while the four least significant output nodes 26 provide the results of shifting or rotating a four bit operand.
As noted above, shifter/rotator 10 operates to shift or rotate four or eight bit operands depending upon the operands provided to input nodes 22 and 24. More specifically, a shift left of an eight bit operand is accomplished by providing the eight bit operand to be shifted to the upper input nodes 20 and logical zeros to each of the lower input nodes 22. A shift right of an eight bit operand is accomplished by providing a logical zero to each of the upper input nodes 20 and the eight bit operand to be shifted to the lower input nodes 22. Rotating an eight bit operand left or right is accomplished by providing the eight bit operand to both the upper and lower input nodes 20 and 22, respectively.
A shift left of a four bit operand is accomplished by providing the four bit operand to be shifted to the four least significant upper input nodes 20, a logical zero to each of the four most significant upper input nodes 20, and a logical zero to each of the lower input nodes 22. Shifting a four bit operand right is accomplished by providing a logical zero to each of the upper input nodes 20, a logical zero to each of the four most significant lower input nodes 22, and the four bit operand to be shifted to the four least significant lower input nodes 22. Rotating a four bit operand either left or right is accomplished by providing the four bit operand to be rotated to the four least significant upper and lower input nodes 20 and 22, respectively, and a logical zero to each of the four most significant upper and lower input nodes 20 and 22, respectively.
Pre-shift stage 12 is configured to receive a sixteen bit operand consisting of the concatenated bits provided to upper and lower input nodes 20 and 22. Pre-shift stage 12 includes a pair of shifting stages which operate to selectively shift the sixteen bit operand left by one and/or realign a four bit operand provided to the four least significant lower input nodes 22. One of the pair of shifting stages includes a first set of multiplexers 44 coupled to and controlled by a pre-shift control node 46. The other shifting stage includes a second set of multiplexers 50 coupled to and controlled by a right shift control node 52. Multiplexers 44 operate to selectively left shift the four bit operand provided to the four least significant lower input nodes 22 in accordance with a control signal provided to pre-shift control node 46. More specifically multiplexers 44 operate to pass either the four bit operand provided to the four least significant lower input nodes 22 when pre-shift control node 46 receives a logical one, or the four logical zeros provided to the four most significant lower input nodes 22 when pre-shift control node 46 receives a logical zero. In general, multiplexers 44 shift or align the four bit operand provided to shifter/rotator when shifter/rotator circuit 10 is employed to rotate a four operand left or right. Multiplexers 50 operate to selectively shift the sixteen bit operand, with or without realignment by multiplexers 44, left by one according to a control signal provided to right shift control node 52. More specifically, multiplexers 50 operate to pass either the fifteen least significant bits of the sixteen bit operand provided thereto when the right shift control node 52 receives a logical one, or the fifteen most significant bits of the sixteen bit operand provided thereto when the right shift control node 52 receives a logical zero. As will be described below, multiplexers 50 of pre-shift stage 12 operate to shift left by one when shifter/rotator 10 is employed to right shift or right rotate a four or eight bit operand.
First shifting stage 14 includes a plurality of two input multiplexers 30 coupled to and controlled by a first shift control node 32. First shifting stage 14 is configured to receive the fifteen bit result operand of pre-shift stage 12. First shift stage 14 operates to selectively shift the result operand left by one bit according to a control signal provided to the first shift control node 32. In other words, first shifting stage 14 operates to pass either the fourteen least significant bits of the fifteen bit result operand provided by pre-shift stage 12 when the first shift control node 32 receives a logical one, or the fourteen most significant bits of the fifteen bit result operand provided by pre-shift stage 12 when the first shift control node 32 receives a zero.
Second shifting stage 16 includes a plurality of two input multiplexers 34 coupled to and controlled by second shift control node 36. Second shifting stage 16 is configured to receive the fourteen bit result operand of the first shifting stage 14. Second shifting stage 16 operates to selectively shift the result operand left by two bits in accordance with a control signal provided to second shift control node 36. In other words, second shifting stage 14 operates to pass either the twelve least significant bits of the fourteen bit result operand provided by first shifting stage 14 when the second shift control node 36 receives a logical one, or the twelve most significant bits of the fourteen bit result operand provided by first shifting stage 14 when the second shift control node 36 receives a logical zero.
Third shifting stage 18 comprises a plurality of two input multiplexers 40 coupled to and controlled by a third shift control node 42. Third shift control node 42 is configured to receive the twelve bit result operand provided by second shifting stage 16. Third shifting stage 18 operates to selectively shift the result operand left by four bits in accordance with a control signal provided to third shift control node 42. In other words, third shifting stage 16 operates to pass either the eight least significant bits of the twelve bit result operand provided by second shifting stage 16 when the third shift control node 42 receives a logical one, or the eight most significant bits of the twelve bit result operand provided by second shifting stage 16 when the third shift control node 42 receives a logical zero.
As noted above, shifter/rotator is a double left shifter which can right shift operands in addition to left shifting operands. Shifter/rotator can also rotate operands left or right. One of ordinary skill in the art will recognize that shifting or rotating an operand right by a designated shift count using a double left shifter is equivalent to shifting or rotating the same operand by the negative of the shift count. Further, one of ordinary skill in the art will recognize that in two's compliment notation, the negative of the shift count equates to the complemented shift count and binary one. Rather than employing a separate circuit to calculate the negative shift count in order to achieve a right shift or a right rotate, the shifter/rotator circuit 10 achieves right shift or a right rotate simply by complementing the shift input provided to control nodes 32, 36 and 42, and by asserting logical one to the right shift control node 52.
As noted above, each shifting stage 12-18 is controlled by corresponding control nodes 32, 36, 42, 46, and 52. Control nodes 32, 36, and 42 receive a shift count provided by an instruction to shift or rotate an operand. Control nodes 52 and 46 receive control signals associated with instructions for right shifting four or eight bit operands and/or rotating four bit operands. For example, when an eight bit operand is to be shifted or rotated left by five bits, control nodes 32, and 42 receive a logical one while control nodes 36, 52 and 46 receive a logical zero. When a four bit operand is to be shifted left by three bits, control nodes 32 and 36 receive a logical one while control node 42, 52 and 46 receive a logical zero. When a four bit operand is to be rotated left by three bits, control nodes 32, 46 and 36 receive a logical one while control node 42 and 52 receive a logical zero.
As can be appreciated, pre-shift stage 12 complicates the design and operation of shifter/rotator 10. More particularly, pre-shift stage 12 is complicated by the presence of the first set of multiplexers 44 coupled to and controlled by the pre-shift control node 46. Shifter/rotator 10 would require an even more complicated pre-shifting stage 12 if shifter/rotator 10 were configured to shift four, eight or sixteen bit operands.
From an inspection of FIG. 1 and the description relating thereto above, it is apparent that operation and implementation of shifter/rotator 10 can be simplified if the first set of multiplexers 44 within pre-shift stage 12 can be eliminated. This would have the effect of reducing the size of the shifter/rotator 10 in addition to increasing its speed of operation.